import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JLayeredPane;
import java.awt.Frame;
import java.awt.Font;
import java.awt.font.FontRenderContext;
import java.awt.font.TextLayout;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.awt.Graphics;
import java.awt.BasicStroke;
import java.awt.Graphics2D;
import java.awt.Dimension;
import java.awt.Color;
import java.awt.GradientPaint;
import java.awt.BorderLayout;
import java.awt.Rectangle;
import java.awt.geom.Rectangle2D;
import java.awt.RenderingHints;
import java.util.HashSet;
import java.util.Vector;
import java.util.Iterator;
import java.util.Random;
 
class DAGnode
{
    String label;
    int time,level;
    double x,y,bestX;
    boolean mark;
    HashSet<DAGnode> inputs;
    HashSet<DAGnode> outputs;
    DAGnode( String name,int t ) {
        label=name;
        time = t;
        x=-1;
        y=-1;
        inputs = new HashSet<DAGnode>();
        outputs = new HashSet<DAGnode>();
    }

    void linkFrom( DAGnode old )
    {
        inputs.add( old );
        System.out.println(old.label + " -> " + label);
    }
    
    boolean linkedFrom( HashSet<DAGnode> set )
    {
        //System.out.println(label + ":linkedFrom(" + set + ") : " + inputs);
        HashSet<DAGnode> intersect = new HashSet<DAGnode>();
        intersect.addAll(set);
        intersect.retainAll(inputs);
        return !intersect.isEmpty();
    }

    boolean linkedFrom( Vector< HashSet<DAGnode> > levels, int top, int bottom )
    {
        for(int i=top; i<=bottom; i++) {
            if( linkedFrom( levels.elementAt(i) ) )
                return true;
        }   
        return false;
    }

}

class DAG
{
    Vector< HashSet<DAGnode> > levels = new Vector< HashSet<DAGnode> >();
    Vector<DAGnode> nodes;

    DAG()
    {
        nodes = new Vector<DAGnode>();
    }

    void generateBinomial(int num, double cost)
    {
        Random r = new Random();
        for(int i=0; i<num; i++)
        {
            String name = "Node " + i;
            DAGnode node = new DAGnode( name,i );
            for(Iterator<DAGnode> ns=nodes.iterator(); ns.hasNext(); )
            {
                DAGnode old = ns.next();
                if( r.nextDouble()<cost )
                    node.linkFrom( old );
            }
            nodes.add( node );
        }
    }

    DAGnode pickRandom( HashSet<DAGnode> set )
    {
        Random r = new Random();
        int indx = r.nextInt( set.size() );
        //System.out.println("Random " + indx + "/" + set.size());
        for(Iterator<DAGnode> it=set.iterator(); it.hasNext(); )
        {
            DAGnode node = it.next();
            if( indx-- == 0 )
                return node;
        }
        return null;    
    }

    void generateLinear(int num, int avgEdges)
    {
        Random r = new Random();

        // Generate layers of uniform(0,num^0.5)
        int maxWidth = (int)Math.sqrt( (double)num )*2;
        if( maxWidth>8 )
            maxWidth=8;
        int count = 1;
        while( nodes.size() < num )
        {
            int lsize = r.nextInt(maxWidth-1)+1;
            HashSet<DAGnode> curLvl = new HashSet<DAGnode>();
            levels.add( curLvl );
            //System.out.print("Level of " + lsize + " ");
            for(int i=0; i<lsize; i++)
            {
                String name = "Node " + count++;
                DAGnode node = new DAGnode( name, count);
                //System.out.print(name + " ");
                node.y = levels.size()-1;
                nodes.add( node ); 
                curLvl.add( node );
            }
            //System.out.println("");
        }

        for(Iterator<DAGnode> ns=nodes.iterator(); ns.hasNext(); )
        {
            DAGnode node = ns.next();
            //System.out.println("Edges to " + node.label + " : " + node.y);
            int numEdges = r.nextInt( avgEdges*2-1 )+1;
            int lvl = (int)node.y;
            // Always pick one edge to previous layer
            if( lvl>0 ) {
                DAGnode src = pickRandom( levels.elementAt( lvl-1 ) );
                node.linkFrom( src );
                numEdges--;
            
                int srcL;
                for(int i=0; i<numEdges; i++)
                {
                    if( lvl==1 )
                        srcL = 0;
                    else {
                        int x = r.nextInt(lvl-1);
                        int y = r.nextInt(lvl-1);
                        if( x > y )
                            srcL = x;
                        else
                            srcL = y;
                    }
                    src = pickRandom( levels.elementAt(srcL) );
                    node.linkFrom( src );
                }
            }
        }
    }

    boolean sharedInput( DAGnode a, DAGnode b )
    {
        HashSet<DAGnode> intersect = new HashSet<DAGnode>( a.inputs );
        intersect.retainAll( b.inputs );
        return !intersect.isEmpty();
    }

    double layoutCost( HashSet<DAGnode> lower)
    {
        double cost = 0;
        for(Iterator<DAGnode> lo=lower.iterator(); lo.hasNext(); )
        {
            DAGnode low = lo.next();
            for(Iterator<DAGnode> hi=low.inputs.iterator(); hi.hasNext(); )
            {
                DAGnode high = hi.next();
                cost += (high.x - low.x) * (high.x - low.x);
            }
        }
        return cost;
    }

    double totalCost()
    {
        double sum=0;
        for(int i=1; i<levels.size(); i++)
            sum += layoutCost( levels.elementAt(i) );
        return sum;
    }

    /* Layout the lower level of nodes randomly, in positions 
     * (0 .. max(lower,higher) )
     */
    void randomLayout( HashSet<DAGnode> lower, int size)
    {
        boolean slots[] = new boolean[size];
        Random r = new Random();
        for(Iterator<DAGnode> lo=lower.iterator(); lo.hasNext(); )
        {
            DAGnode low = lo.next();
            int pos;
            do {
                pos = r.nextInt(size);
            }
            while( slots[ pos ] == true );
            low.x = (double)pos;
            slots[ pos ] = true;
        }
    }

    void saveLayout( HashSet<DAGnode> level )
    {
        for(Iterator<DAGnode> it=level.iterator(); it.hasNext(); )
        {
            DAGnode node = it.next();
            node.bestX = node.x;
        }
    }

    void retrieveLayout( HashSet<DAGnode> level )
    {
        for(Iterator<DAGnode> it=level.iterator(); it.hasNext(); )
        {
            DAGnode node = it.next();
            node.x = node.bestX;
        }
    }


    void expandCoords()
    {
        for(Iterator<DAGnode> it=nodes.iterator(); it.hasNext(); )
        {
            DAGnode node = it.next();
            node.x = node.x*128+200;
            node.y = node.y*64 +32 ;
        }
    }

    void layout(Rectangle bounds)
    {
/*        HashSet<DAGnode> allowed = new HashSet<DAGnode>();
        for( Iterator<DAGnode> i=nodes.iterator(); i.hasNext(); )
            i.next().mark = false;
        int level=0;

        while(allowed.size() < nodes.size()) 
        {
            HashSet<DAGnode> current = new HashSet<DAGnode>();
            levels.add( current );
            int pos=0;

            for(Iterator<DAGnode> i=nodes.iterator(); i.hasNext();  ) {
                DAGnode n = i.next();
                //System.out.println(current.toString());
                if( !n.mark && allowed.containsAll( n.inputs ) )
                {
                    n.level = level;
                    //n.x = pos++ * 128 + 32;
                    n.y = level*60 + 32;
                    n.mark = true;
                    current.add(n);
                    //System.out.println("Layout: " + n.toString() + ": " + n.label + " " + n.x + "," + n.y);
                    //System.out.println(levels.toString());
                }
            }
            allowed.addAll( current );
            level++;
        }
        //System.out.println("Greedy total cost: " + totalCost() );
*/
        int width=0;
        for(int i=0; i<levels.size(); i++)
            if( levels.elementAt(i).size() > width)
                width = levels.elementAt(i).size();
        double bestTotalCost = 1000000;
        for(int its=0; its<100; its++) {
            for(int i=0; i<levels.size(); i++)
                randomLayout( levels.elementAt(i), width );
            double cost = totalCost();
            if( cost < bestTotalCost ) {
                bestTotalCost = cost;
                System.out.println("Total cost: " + totalCost() );
                for(int i=0; i<levels.size(); i++)
                    saveLayout( levels.elementAt(i) );
            }
        }
        for(int i=1; i<levels.size(); i++)
            retrieveLayout( levels.elementAt(i) );
    
        expandCoords();
    }

    void draw(Graphics2D g)
    {
        double width=-1, height=-1;
        FontRenderContext frc = g.getFontRenderContext();
        Font font = g.getFont();
        for( Iterator<DAGnode> i=nodes.iterator(); i.hasNext(); ) {
            DAGnode n=i.next();
            TextLayout layout = new TextLayout( n.label,font,frc );
            Rectangle2D bounds = layout.getBounds();
            if( bounds.getWidth()>width )
                width = bounds.getWidth()+1;
            if( bounds.getHeight()>height )
                height = bounds.getHeight()+1;
        }
        g.setStroke( new BasicStroke( 5, BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND ));
        for( Iterator<DAGnode> i=nodes.iterator(); i.hasNext(); ) {
            DAGnode n=i.next();
            for( Iterator<DAGnode> in=n.inputs.iterator(); in.hasNext(); ) {
                DAGnode inNode = in.next();
                g.setPaint( new Color(0.8f,0.3f,0.3f) );
                g.drawLine( (int)inNode.x+32 , (int)inNode.y+16, (int)n.x + 32, (int)n.y+16 );
                
            }
        }
        for( Iterator<DAGnode> i=nodes.iterator(); i.hasNext(); ) {
            DAGnode n=i.next();
            //System.out.println("Node: " + n.label + " @ " + n.x + "," + n.y);
            g.setPaint( new Color(0.5f,0.5f,0.5f) );
            g.fill( new Rectangle( (int)n.x-5, (int)n.y-5, (int)width+10, (int)height+10) );
            g.setPaint( new Color(0,0,0) );
            g.fill( new Rectangle( (int)n.x-2, (int)n.y-2, (int)width+4, (int)height+4) );
            g.setPaint( new Color(1f,1f,1f));
            g.drawString(n.label,(float)n.x,(float)(n.y+height));
        }
    }
}


class GuiListener extends WindowAdapter
{
    public void windowClosing(WindowEvent e) {
        System.exit(0);
    }
}

class Backdrop extends JLabel {

    DAG dag;
    boolean firstTime=true;
    Backdrop(DAG d) {
        dag=d;
        setFont( getFont().deriveFont(16f));
    }

    public void paintComponent( Graphics g ) {
        Graphics2D g2 = (Graphics2D)g;
        RenderingHints rh = new RenderingHints( RenderingHints.KEY_ANTIALIASING,
                                                RenderingHints.VALUE_ANTIALIAS_ON);
        rh.put( RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY);
        g2.setRenderingHints( rh );
        Rectangle bs = getBounds();
        g2.setPaint( new GradientPaint( bs.width/4,bs.height/4, new Color(0.7f,0.6f,0.3f), 
                                (bs.width*3)/4,(bs.height*3)/4, new Color(0.8f,0.65f,0.4f)));
        g2.fill( bs );
        if( firstTime ) 
            dag.layout(getBounds());
        firstTime=false;
        dag.draw(g2);
        //super.paintComponent(g);
    }
}

public class Gui{
    JFrame window;
    boolean fs;

    public Gui(DAG dag)
    {
        window = new JFrame("AC.net");
        window.addWindowListener(new GuiListener());
        window.setSize(640,512);
        Backdrop b = new Backdrop(dag);
        window.getContentPane().add(b);

        fs = true;
        fullScreen(!fs);
    }
    void fullScreen(boolean mode) {
        if( mode!=fs ) {
            //window.setVisible(false);    
            if( mode )
                window.setExtendedState(Frame.MAXIMIZED_BOTH);
            else
                window.setExtendedState(0);
            window.setUndecorated(mode);
            window.validate();
            window.setVisible(true);    
        }
    }
    public static void main(String[] args) {
        int number = 15, avgEdges=3;
        double cost= 0.5;
        for(int i=0; i<args.length; i++) {
            if( args[i].charAt(0) == '-' ) {
                switch( args[i].charAt(1) )
                {
                    case 'n':
                        number = Integer.parseInt( args[i].substring(2) );
                        break;
                    case 'p':
                        cost = Double.parseDouble( args[i].substring(2) );
                        break;
                    case 'e':
                        avgEdges = Integer.parseInt( args[i].substring(2) );
                        break;
                }
            }
        }
        DAG dag = new DAG();
        dag.generateLinear(number,avgEdges);
        Gui x = new Gui(dag);
    }
}
